public class JumpFloor {
    // 跳台阶
    // https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int jumpFloor (int number) {
        // write code here
        // dp[i]表示跳到第i阶台阶有多少种跳法
        // 状态转移方程：因为一次可以跳一级和两级，所以dp[i] = dp[i-1] + dp[i+2]
        int[] dp = new int[number+1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= number; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[number];
    }

    /**
     * 空间优化， 因为根据状态转移方程我们可以知道，在填表的时候只需要知道dp[i-1]和dp[i-2]的状态
     * 所以可以只使用两个变量来维护这两个状态就可以了
     * @param number
     * @return
     */
    public int jumpFloor1 (int number) {
        // write code here
        // dp[i]表示跳到第i阶台阶有多少种跳法
        // 状态转移方程：因为一次可以跳一级和两级，所以dp[i] = dp[i-1] + dp[i+2]
        int num1 = 1, num2 = 1;
        for (int i = 2; i <= number; i++) {
            int tmp = num1 + num2;
            num1 = num2;
            num2 = tmp;
        }
        return num2;
    }
}
